package Leetcode100Hot;

import java.util.Arrays;

/*
最短无序连续子数组
给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。
请你找出符合题意的 最短 子数组，并输出它的长度。

示例 1：
输入：nums = [2,6,4,8,10,9,15]
输出：5
解释：你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。
示例 2：
输入：nums = [1,2,3,4]
输出：0
示例 3：
输入：nums = [1]
输出：0

提示：
1 <= nums.length <= 104
-105 <= nums[i] <= 105
进阶：你可以设计一个时间复杂度为 O(n) 的解决方案吗？
 */
public class _95最短无序连续子数组 {

    //Sort + 比对
    //nlog(n) O(n)
    //7ms
    public int findUnsortedSubarray(int[] nums) {
        int n = nums.length;
        int[] tmp = new int[n];
        //优化
        /*
        for (int i = 0; i < n; i++) {
            tmp[i] = nums[i];
        }
        */
        //copy nums 从0索引开始 到 tmp 中 从0索引开始 copy n个
        System.arraycopy(nums, 0, tmp, 0, n);
        Arrays.sort(tmp);
        int left = 0, right = n - 1;
        while (left < n && nums[left] == tmp[left]) left++;
        while (right >= 0 && nums[right] == tmp[right]) right--;
        if (left > right) return 0;
        return right - left + 1;
    }

    //官解：方法二：一次遍历
    //O(n) O(1)
    //1ms
    /*
    作者：力扣官方题解
    链接：https://leetcode.cn/problems/shortest-unsorted-continuous-subarray/solutions/911677/zui-duan-wu-xu-lian-xu-zi-shu-zu-by-leet-yhlf/
     */
    class Solution {
        public int findUnsortedSubarray(int[] nums) {
            int n = nums.length;
            int maxn = Integer.MIN_VALUE, right = -1;
            int minn = Integer.MAX_VALUE, left = -1;
            for (int i = 0; i < n; i++) {
                if (maxn > nums[i]) {
                    right = i;
                } else {
                    maxn = nums[i];
                }
                if (minn < nums[n - i - 1]) {
                    left = n - i - 1;
                } else {
                    minn = nums[n - i - 1];
                }
            }
            return right == -1 ? 0 : right - left + 1;
        }
    }

}
